package someTestExcemple.huaweiOd.dp;
//华为OD机试 - 猴子爬山 - 动态规划（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/130938236
import java.util.*;
public class MonkeyClimb {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        if(input<=0 || input > 50){
            System.out.println("请输入0到50之间的数字");
            return;
        }

        System.out.println(calculation(input));
    }
    private static int calculation(int step){
        //只剩一个台阶了
        if (step < 3){
            return 1;
        }
        //剩下的场景都需要分成当前跳1步或者跳3步
        return calculation(step -1) + calculation( step -3);
    }

}
